/*
 * Подстроки
 *  - Наивный алг.
 *  - Рабина-Карпа
 *  - КМП
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>
#include <math.h>

#define MAX(a, b)	((a) > (b) ? (a) : (b))

static unsigned int *_offsets = NULL;
static unsigned int _offsets_n = 0;
static unsigned int _offsets_size = 0;

char *
my_strstr(const char *s1, const char *s2)
{
	unsigned long int i=0, j=0;

	while (s1[i] != '\0') {
		if (s1[i] == *s2) {
			while (s2[j] != '\0' && s1[i + j] == s2[j])
				++j;

			if (s2[j] == '\0')
				return (char *) (s1 + i);
			else {
				j = 0;
				++i;
			}
		} else
			++i;
	}
	return (char*) 0;
}

char *
gen_random_text(const unsigned int len, const unsigned int p)
{
	char	*data = NULL;
	int	i = 0;

	data = calloc(len + 1, sizeof (char));
	while (i < len) {
		data[i] = 'a' + (rand() % p);
		//data[i] = 0x20 + (rand() % p);
		i++;
	}
	data[len] = '\0';

	return data;
}

void
add_valid_offset(const unsigned int s)
{
	if (_offsets == NULL) {
		_offsets = (unsigned int *) calloc(4, sizeof *_offsets);
		_offsets_size = 4;
	}

	if (_offsets_n >= _offsets_size)
		_offsets = (unsigned int *) realloc(_offsets, (_offsets_size *= 2));

	_offsets[_offsets_n++] = s;
}

char *
rabin_karp(const char *str, const unsigned int n, const char *substr,
		const unsigned int m, const unsigned int ac)
{
	//const long long	q = 4611686018427387847LL;
	const long long	q = 1073741789;
	long long	h = (long long) powl((long double) ac, (long double) m - 1.L) % q;
	long long	p = 0;
	long long	t = 0;
	unsigned int	i = 0;

	for (i = 0; i < m; ++i) {
		t = (ac * t + (str[i] - 0x20)) % q;
		p = (ac * p + (substr[i] - 0x20)) % q;
	}

	for (i = 0; i < n - m; ++i) {
		if (t == p && strncmp(str + i, substr, m) == 0)
			add_valid_offset(i);
			//return str + i;
		if (i < n - m)
			t = (ac * (t - h * (str[i] - 0x20)) + (str[i + m] - 0x20)) % q;
	}

	return NULL;
}

void
print_prefix_func_and_string(const char *str, unsigned int *p)
{
	long i = 0;
	long n;

	fprintf(stderr, "{ ");
	while (str[i]) {
		fprintf(stderr, "\'%c\', ", str[i++]);
	}
	fprintf(stderr, "}\n");
	n = i;

	fprintf(stderr, "{ ");
	for (i = 0; i < n; i++) {
		fprintf(stderr, "%2d , ", p[i]);
	}
	fprintf(stderr, "}\n");
}

unsigned int *
compute_prefix_func(const char *str, const unsigned int m)
{
	unsigned int *p = NULL;
	unsigned int k = 0;
	unsigned int q = 1;

	p = (unsigned int *) calloc(m, sizeof *p);
	//p[0] = 0; //what we would have to do if we were using malloc()
	for (; q < m; ++q) {
		while (k > 0 && str[k] != str[q])
			k = p[k - 1];
		if (str[k] == str[q])
			k++;
		p[q] = k;
	}

	print_prefix_func_and_string(str, p);

	return p;
}

char *
kmp(const char *text, const unsigned int n, const char *str, const unsigned int m)
{
	unsigned int *p = NULL;
	unsigned int q = 0;
	unsigned int i = 0;

	p = compute_prefix_func(str, m);

	for (; i < n; ++i) {
		while (q > 0 && str[q] != text[i])
			q = p[q - 1];
		if (str[q] == text[i])
			q++;
		if (q == m) {
			add_valid_offset(i - m + 1);
			q = p[q - 1];
		}
	}

	free(p);

	return NULL;
}

int
main(void)
{
	int		alg_id = -1;
	char		is_random = -1;
	unsigned int	n, m, p; //text length, substring length, alphabet complexity
	char		*text = NULL,
			*substring = NULL;
	int		i = 0;
	char		*tmp = NULL;
	double		timer = 0;
	char		*buffer;

	(void) fprintf(stderr, "algorithm id: ");
	(void) scanf("%d", &alg_id);
	(void) fprintf(stderr, "randomize string? [y/n] ");
	(void) scanf("%*c%c", &is_random);
	is_random = (is_random == 'y' || is_random == 'Y') ? 1 : 0;
	(void) fprintf(stderr, "Text length, substring length and alphabet complexity: ");
	(void) scanf("%d%d%d", &n, &m, &p);

	_offsets = (unsigned int *) malloc(n - m + 1UL);
	_offsets_size = n - m + 1UL;

	if (is_random) {
		(void) fputs("generating random strings\n", stderr);
		text = gen_random_text(n, p);
		substring = gen_random_text(m, p);
	} else {
		text = (char *) calloc(n + 1, sizeof *text);
		substring = (char *) calloc(m + 1, sizeof *substring);

		buffer = (char *) malloc(MAX(n + 1, m + 1));

		do {
			(void) fgets(buffer, MAX(n + 1, m + 1), stdin);
		} while (sscanf(buffer, "%[^\n\r\t]", text) == 0);
		n = strlen(text);

		do {
			(void) fgets(buffer, MAX(n + 1, m + 1), stdin);
		} while (sscanf(buffer, "%[^\n\r\t]", substring) == 0);
		m = strlen(substring);

		free(buffer);
	}

	timer = clock();

	if (alg_id == 1) {
		tmp = text - 1;
		while ((tmp = my_strstr(tmp + 1, substring))) //thankyou clang
			add_valid_offset(tmp - text);
	} else if (alg_id == 2) {
		rabin_karp(text, n, substring, m, p);
	} else if (alg_id == 3) {
		kmp(text, n, substring, m);
	}

	printf("%u matches\nTotal time: %gs\n", _offsets_n, ((double) clock() - timer) / CLOCKS_PER_SEC);
#ifdef DEBUG
	for (i = 0; i < _offsets_n; i++)
		(void) printf("%u ", _offsets[i]);
	putc('\n', stdout);
	(void) printf("\ntext=%s\nsubstr=%s\n", text, substring);
#endif

	free(text);
	free(substring);
	free(_offsets);
exit:
	return 0;
}
